package com.sk.leetcode.arithmetic;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 * <p>
 * 百度百科中最近公共祖先的定义为：
 * “对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 * <p>
 * 解析：改变下tree结构，实现就变得很简单。
 */
public class Test236 {
    public static void main(String[] args) {
        Integer[] h = {3, 5, 1, 6, 2, 0, 8, null, null, 7, 4, null, null, null, null};
        List<TreeNode> nodes = Test124.suan(h);

        TreeNode res = lowestCommonAncestor(nodes.get(0), new TreeNode(10) , new TreeNode(50));
        System.out.println(res!=null?res.val:null);
    }

    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pListone = new ArrayList<>();
        List<TreeNode> pListtwo = new ArrayList<>();

        boolean bone = preTreeNode(pListone, root, p);
        if(bone) {
            pListone.add(root);
        }
        boolean btwo = preTreeNode(pListtwo, root, q);
        if(btwo) {
            pListtwo.add(root);
        }
        if(!btwo || !bone) {
            if(!btwo && !bone) {
                return null;
            }
            if(!bone) {
                return q;
            }
            if(!btwo) {
                return p;
            }
        }
        Collections.reverse(pListone);
        Collections.reverse(pListtwo);
        int index = 0;
        while (index < pListone.size() && index < pListtwo.size()) {
            if(pListone.get(index).val == pListtwo.get(index).val) {
                index++;
            } else {
                return pListone.get(--index);
            }
        }
        if(pListone.size() > pListtwo.size()) {
            return pListtwo.get(pListtwo.size()-1);
        }else {
            return pListone.get(pListone.size()-1);
        }
    }

    private static boolean preTreeNode(List<TreeNode> pList, TreeNode root, TreeNode p) {
        if(root == null) {
            return false;
        }
        if(root.val == p.val) {
            return true;
        } else {
            boolean bl = preTreeNode(pList, root.left, p);
            if(bl) {
                pList.add(root.left);
                return true;
            }
            boolean br = preTreeNode(pList, root.right, p);
            if(br) {
                pList.add(root.right);
                return true;
            }
            return false;
        }
    }

}
